package com.cqs.leetcode.string;

import com.cqs.leetcode.ds.ArraysUtils;
import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/8/16
 */
public class PartitionLabels763 {


    public List<Integer> partitionLabels(String S) {
        char[] chars = S.toCharArray();
        //每个字母的右边界
        int[] rboard = new int[26];
        int left = 0;
        int right;
        List<Integer> list = new ArrayList<>();
        while (left < chars.length) {
            right = chars.length - 1;
            char c = chars[left];
            while (chars[right] != c) --right;
            //求出当前字符c的右边界
            rboard[c - 'a'] = right;
            //继续查看[left,right]之间的所有字母是否均落在当前区间
            //若有不在当前区间的字符，需要扩展区间
            int idx = left;
            int r = chars.length - 1;
            while (++idx < right && r > right) {
                c = chars[idx];
                //已经求过
                if (rboard[c - 'a'] != 0) continue;
                //求c的边界
                while (chars[r] != c && r > right) {
                    --r;
                }
                if (r > right){
                    //更新边界
                    rboard[c - 'a'] = r;
                    right = r;
                }
                r = chars.length - 1;
            }
            //添加第i组
            list.add(right - left + 1);
            left = right + 1;
        }
        return list;
    }

    public static void main(String[] args) {
        PartitionLabels763 part = new PartitionLabels763();
        List<String> test = Lists.newArrayList("adefegdez", "ababcbacadefegdehijhklij", "abcdefg");
        test.forEach(it -> {
            System.out.println(it + "\t" + part.partitionLabels(it));
        });
    }
}
